package com.kevinkk.hashmap;

import java.util.Map;
import java.util.HashMap;

/**
 * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
 * 0 <= i, j, k, l < n
 * nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 */

/**
 * 这道题不需要进行去重，因此可以直接用 HashMap 来处理
 * map 中记录了 nums1 和 nums2 中所有数字组合的和，以及出现的次数
 * 我们只用在 nums3 和 nums4 中找有没有对应的互补的数存在就好了（类似 TwoSum 的处理）
 */

public class FourSumII {
    class Solution {
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i : nums1) {
                for (int j : nums2) {
                    map.put(i + j, map.getOrDefault(i + j, 0) + 1);
                }
            }

            int res = 0;
            for (int i : nums3) {
                for (int j : nums4) {
                    res += map.getOrDefault(-i - j, 0);
                }
            }

            return res;
        }
    }
}
